package com.test.dag;

import java.util.*;

/**
 * 定义图结构
 *
 * @author yulongtian
 * @create 2024-12-28 16:07
 */
public class DirectedGraph {
    private Map<Integer, List<Integer>> adjList;  // 邻接表
    private Map<Integer, Integer> inDegree;       // 记录每个节点的入度

    // 构造函数
    public DirectedGraph() {
        adjList = new HashMap<>();
        inDegree = new HashMap<>();
    }

    // 添加边
    public void addEdge(int u, int v) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.get(u).add(v);

        inDegree.put(v, inDegree.getOrDefault(v, 0) + 1);
        inDegree.putIfAbsent(u, 0);  // 如果节点u没有出度，初始化入度为0
    }

    // 拓扑排序
    public List<Integer> topologicalSort() {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        // 找到所有入度为0的节点
        for (int node : inDegree.keySet()) {
            if (inDegree.get(node) == 0) {
                queue.offer(node);
            }
        }

        // 遍历所有入度为0的节点
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            // 遍历当前节点的邻接节点
            if (adjList.containsKey(current)) {
                for (int neighbor : adjList.get(current)) {
                    // 每次移除一条边时，更新入度
                    inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                    // 如果某个邻接节点的入度变为0，加入队列
                    if (inDegree.get(neighbor) == 0) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        // 如果结果列表的长度等于图中节点的数量，说明图是DAG并且拓扑排序成功
        if (result.size() != inDegree.size()) {
            System.out.println("图包含环，无法进行拓扑排序");
            return new ArrayList<>();  // 返回空列表表示拓扑排序失败
        }

        return result;
    }
}
